#include <stdio.h>
#include <stdlib.h>

/**
 * 二叉树节点
 */
typedef struct TreeNode {
    char data;
    struct TreeNode * left, * right;
} * Tree;

/**
 * 栈
 */
typedef struct StackNode {
    // 栈中存储的是二叉树节点
    Tree treeNode;
    struct StackNode * next;
} * Stack;

/**
 * 队列
 */
typedef struct QueueNode {
    Tree treeNode;
    struct QueueNode * next;
} * QueueNode;
// 队列的头尾指针
typedef struct Queue {
    struct QueueNode * front, * rear;
} * Queue;

/**
 * 栈空判断
 */
_Bool isEmpty(Stack stack) {
    return stack->next == NULL;
}

/**
 * 栈初始化
 */
void initStack(Stack stack) {
    stack->next = NULL;
}

/**
 * 入栈
 */
void pushStack(Stack stack, Tree root) {
    struct StackNode * newStackNode = malloc(sizeof (Stack));
    newStackNode->next = stack->next;
    newStackNode->treeNode = root;
    stack->next = newStackNode;
}

/**
 * 出栈
 */
Tree popStack(Stack stack) {
    struct StackNode * topStackNode = stack->next;
    stack->next = topStackNode->next;
    Tree pNode = topStackNode->treeNode;
    free(topStackNode);
    return pNode;
}

void visit(Tree root) {
    printf("%c\t", root->data);
}

void preOrder(Tree root) {
    struct StackNode stack;
    struct TreeNode * p = root;
    initStack(&stack);
    while (p || !isEmpty(&stack)) {
        if(p) {
            visit(p);
            pushStack(&stack, p);
            p = p->left;
        }
        else {
            p = popStack(&stack);
            p = p->right;
        }
    }
}

void inOrder(Tree root) {
    struct StackNode stack;
    initStack(&stack);
    struct TreeNode * p = root;
    while (p || !isEmpty(&stack)) {
        if(p) {
            pushStack(&stack, p);
            p = p->left;
        } else {
            p = popStack(&stack);
            visit(p);
            p = p->right;
        }
    }
}

Tree getTopTreeNode(Stack stack) {
    return stack->next->treeNode;
}

void postOrder(Tree root) {
    struct StackNode stack;
    initStack(&stack);
    struct TreeNode * p = root;
    // 用于标记右孩子是否已被访问
    struct TreeNode * rightFlag = NULL;
    while (p || !isEmpty(&stack)) {
        if(p) {
            pushStack(&stack, p);
            p = p->left;
        } else {
            // 仅获取栈顶元素
            p = getTopTreeNode(&stack);
            // 有右孩子且未被访问过
            if(p->right && p->right != rightFlag) {
                p = p->right;
            } else {
                p = popStack(&stack);
                visit(p);
                // 标记访问过的节点并重置p指针
                rightFlag = p;
                p = NULL;
            }
        }
    }
}

/**
 * 初始化队列
 */
void initQueue(Queue queue) {
    QueueNode qNode = malloc(sizeof (QueueNode));
    queue->front = queue->rear = qNode;
}

/**
 * 入队
 */
void enQueue(Queue queue, Tree root) {
    QueueNode newQNode = malloc(sizeof (QueueNode));
    newQNode->next = queue->rear->next;
    newQNode->treeNode = root;
    queue->rear->next = newQNode;
    queue->rear = newQNode;
}

/**
 * 出队
 */
Tree deQueue(Queue queue) {
    struct QueueNode * tempNode = queue->front->next;
    Tree pNode = tempNode->treeNode;
    queue->front->next = tempNode->next;
    // 队列只剩一个元素的情况
    if(tempNode == queue->rear) {
        queue->rear = queue->front;
    }
    free(tempNode);
    return pNode;
}

/**
 * 队列判空操作
 */
_Bool isEmptyQueue(Queue queue) {
    return queue->front == queue->rear;
}

/**
 * 层次遍历
 */
void levelOrder(Tree root) {
    struct Queue queue;
    initQueue(&queue);
    enQueue(&queue, root);
    while (!isEmptyQueue(&queue)) {
        root = deQueue(&queue);
        visit(root);
        // 看当前节点是否有左右孩子，有就全部入队
        if(root->left) {
            enQueue(&queue, root->left);
        }
        if(root->right) {
            enQueue(&queue, root->right);
        }
    }
}





int main() {
    struct TreeNode * A = malloc(sizeof (Tree));
    struct TreeNode * B = malloc(sizeof (Tree));
    struct TreeNode * C = malloc(sizeof (Tree));

    A->data = 'A';
    B->data = 'B';
    C->data = 'C';
    A->left = B;
    A->right = C;
    B->left = B->right = NULL;
    C->left = C->right = NULL;


//    preOrder(A);
//    printf("\n");
//    inOrder(A);
//    printf("\n");
//    postOrder(A);
//    printf("\n");
    levelOrder(A);
}


